package com.zp.self.module.level_4_算法练习.算法.排序;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author By ZengPeng
 */
public class III_插入排序_O_n2 {
    static int move = 0;
    @Test
    public void main() {
        int[] ints = {7, 6, 5, 4, 3, 2, 1,0};
        new III_插入排序_O_n2().insertSort(ints);
        System.out.println(Arrays.toString(ints ));
    }

    /**
    题目： 插入排序 ：时间：O(n*n) 、空间：O(1)、顺序稳定

    分析：将数组中的元n素分为一个已排序区间和一个未排序区间，
         1.开始时：已排序区间 中只包含一个元素，未排序区间中包含有 n-1 个元素，
         2.排序过程中每次从 未排序区间 中取出第一个元素，与 已排序区间 中的元素进行比较，
         3.将它插入到 已排序区间 中的适当位置，使之成为新的 已排序区间，直到 未排序区间 的元素为空。
     **/
    public void insertSort(int[] arr){
        //从1下标开始，默认0下标为初始排序区间
        for (int i = 1; i < arr.length; i++) {
            //cur记录当前指针的值  preIndex记录前一个指针
            int cur = arr[i],proIndex=i-1;
            while (proIndex>-1 && arr[proIndex]>cur){//--这里对比希尔排序：可能需要与前面的所有值作比较
                arr[proIndex+1] = arr[proIndex];//将前一个数的值 向后位移一个
                proIndex--;//向前位移，找更小的比较
                move++;
            }
            arr[proIndex+1] = cur;//把cur插入有序区间
        }
        System.out.println("移动次数："+move);
    }

}
